package zuo.baseUP2_Sorted_UnionField;

import sun.net.idn.Punycode;

import java.util.HashMap;
import java.util.List;
import java.util.Stack;

/**
 * @Author: Forx
 * @Data: 2021/6/17
 * @Desc: Algorithm - zuo.baseUP2_Sorted_UnionField
 * @Version: v1.0
 */
public class UnionFind {
    public static class Element<V>{
        public V value;

        public Element(V value) {
            this.value = value;
        }
    }
    /**
     * findHead 掉用的次数越多越接近o(1)
     * */
    public static class UnionFindSet<V>{
        public HashMap<V,Element<V>> elementHashMap;
        public HashMap<Element<V>,Integer> sizeHashMap;
        public HashMap<Element<V>,Element<V>> fatherHashMap;

        public UnionFindSet(List<V> list) {
            elementHashMap = new HashMap<>();
            fatherHashMap = new HashMap<>();
            sizeHashMap = new HashMap<>();
            for(V v:list){
                Element<V> element = new Element<>(v);
                elementHashMap.put(v,element);
                fatherHashMap.put(element,element);
                sizeHashMap.put(element,1);
            }
        }

        private Element<V> findHead(Element<V> element){
            Stack<Element<V>> path = new Stack<>();
            while (element!=fatherHashMap.get(element)){
                path.push(element);
                element = fatherHashMap.get(element);
            }
            while (!path.isEmpty()){
                fatherHashMap.put(path.pop(),element);
            }
            return element;

        }
        public boolean isSameSet(V a,V b){
            if(elementHashMap.containsKey(a) && elementHashMap.containsKey(b)){
                return findHead(elementHashMap.get(a)) == findHead(elementHashMap.get(b));
            }
            return false;
        }

        public void union(V a,V b){
            if(elementHashMap.containsKey(a) && elementHashMap.containsKey(b)){
                Element<V> aF = findHead(elementHashMap.get(a));
                Element<V> bF = findHead(elementHashMap.get(b));
                if(aF!=bF){
                    Element<V> bigger = sizeHashMap.get(aF) > sizeHashMap.get(bF) ? aF:bF;
                    Element<V> smaller = bF==bigger?aF:bF;
                    fatherHashMap.put(smaller,bigger);
                    sizeHashMap.put(bigger,sizeHashMap.get(bF) + sizeHashMap.get(aF));
                    sizeHashMap.remove(smaller);

                }

            }
        }
    }
}
